package com.github.kezhenxu94.playground.java.atoffer;

/**
 * 斐波那契数列
 * 
 * 大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。
 * 
 * n<=39
 * 
 * @author ke.zhen.xu
 *
 */
public class AtOfferFibonacci {

	/**
	 * Recursive Version
	 * Time Limited
	 * @param n
	 * @return
	 */
	public int fibonacciRecursive(int n) {
		if (n == 0 || n == 1)
			return n;
		return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
	}
	
	public int fibonacciIterative(int n) {
		if (n == 0 || n == 1)
			return n;
		int nMinus1 = 1;
		int nMinus2 = 0;
		n -= 2;
		while (n-- > 0) {
			int temp = nMinus1 + nMinus2;
			nMinus2 = nMinus1;
			nMinus1 = temp;
		}
		return nMinus1 + nMinus2;
	}
}
